//
// Created by Semir on 2020/6/5.
//

#include <iostream>
#include "../Util/Tree.h"

using namespace std;

int cnt = 0;
TreeNode* target;

void InOrderTravel(TreeNode* pRoot, int k) {
    if (pRoot == nullptr || target != nullptr) {
        return;
    }
    if (pRoot->left != nullptr) {
        InOrderTravel(pRoot->left, k);
    }
    cnt++;
    if (cnt > k) {
        return;
    } else if (cnt == k) {
        target = pRoot;
        return;
    }
    if (pRoot->right != nullptr) {
        InOrderTravel(pRoot->right, k);
    }
}

TreeNode* KthNode(TreeNode* pRoot, int k) {
    target = nullptr;
    InOrderTravel(pRoot, k);
    return target;
}

int main() {
    TreeNode* root = TestTree6();
    TreeNode* node = KthNode(root, 3);
    cout << endl << node->val << endl;
    return 0;
}
